#include <iostream>
#include <vector>
#include <cassert>
#include <unordered_map>

using namespace std;

// 1: 无序数组
/**
 * 1.排序后双索引对撞 O(nlogn) + O(n)
 * 2. 将每个元素放入查找表,查找 target - a 是否存在 O(n)
 */
class Sum {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
		unordered_map<int, int> map;	// 存储对应元素及其索引值
       // 遍历查找表 只遍历v 前面元素，查找是否满足和为target,
		for(int i = 0; i < nums.size(); i++){
			// 确立要查找的元素
			int complement = target - nums[i];
			// 在当前查找表查找是否存在该元素
			if(map.find(complement) != map.end()){ // 能找到
				// 创建数组 (当前索引值, complement对应的索引值)
				int res[2] = {i, map[complement]};
				
				// 数组初始化vector 类
				return vector<int>(res, res + 2);
			}
			
			// 没有找到 ，将 nums[i] 放入查找表,继续循环
			record[nums[i]] = i;
		} 
		
		throw invalid_argument("the input has no solution!");
    }
};
